import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;


public class Bag implements Set<Object> {

	HashMap<Object,Integer> store;
	
	Bag(){
		store = new HashMap<Object, Integer>();
	}

	public int size() {
		Iterator<Integer> i =store.values().iterator();
		int ret=0;
		while(i.hasNext())
			ret += i.next();
		return ret;
	}
	public boolean add(Object e) {
		int c;
		if (e != null){
			if(contains(e))
				c = store.get(e)+1;
			else
				c=1;
			store.put(e, c);
			return true;
		}
		return false;
	}

	public void clear() {
		store.clear();
	}
	public boolean contains (Object o) {
		return store.containsKey(o);
	}
	//public boolean containsAll(Object c) {
		
	public boolean isEmpty() {
		return (store.isEmpty()); 
	}
	public boolean remove(Object o) {
		if(store.get(o).intValue() > 1)
			return (store.put(o, store.get(o).intValue()-1) != null) ?  true : false ;
		return (store.remove(o) != null ) ? true : false;

	}
	public boolean removeAll(Collection<? extends Object> c) {
		Iterator<? extends Object> i = c.iterator();
		boolean b = false;
		while(i.hasNext())
			b |= remove(i.next());
		return b;
	} 
	
	public boolean addAll(Collection<? extends Object> e) {
		Iterator<? extends Object> i = e.iterator();
		boolean b = false;
		while (i.hasNext())
			b |= add(i.next());
		return b;
	}
	
	public boolean containsAll(Collection<? extends Object> c) {
		Iterator<? extends Object> i = c.iterator();
		boolean b = false;
		while(i.hasNext())
			b |= contains(i.next());
		return b;
	}
	
	public Iterator<Object> iterator() {
		return new BagIterator();
 	}
	class BagIterator implements java.util.Iterator<Object>{
		Object cur= null;
		int val = 0;
		Iterator<Integer> v = store.values().iterator();
		Iterator<Object> k = store.keySet().iterator();
		public boolean hasNext() {
			return (k.hasNext() || val > 0);
				
		}

		
		public Object next() {
			if (hasNext()){
				if (val >= 1){
					val--;
					return cur;
				}
				cur = k.next();
				val = v.next()-1;
				return cur;
			}
			throw new java.util.NoSuchElementException();  
		}

		public void remove() {
			throw new UnsupportedOperationException("");
		}
	
		
	}
	
	public boolean retainAll(Collection<? extends Object> c) {
		Iterator<? extends Object> i = c.iterator();
		boolean b = false;
		Object o;
		HashMap<Object, Integer> h = new HashMap<Object, Integer>();
		while(i.hasNext()){
			o = i.next();
			if(contains(o)){
				if (h.containsKey(o))
					h.put(o, h.get(o).intValue()+1);
				h.put(o, 1);
			}
		}
		store = h;
		b = true;
		return b;
	}

	public Object[] toArray() {
		Iterator<Object> i = iterator();
		Object[] o = new Object[size()];
		int c = 0;
		while(i.hasNext()){
			o[c]= i.next();
			c++;
		}
		return o;
	}

	public <T> T[] toArray(T[] a) {
		throw new UnsupportedOperationException() ;

	}



}
